package interviewClassic150;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Tecent1 {
    class Trie {
        public boolean isEnd;
        public Map<Character,Trie> next;

        public Trie() {
            next = new HashMap<>();
            isEnd = false;
        }

        public void insert(String s) {
            Trie node = this;
            for (int i = 0; i < s.length(); i++) {
                char curChar = s.charAt(i);
                Trie nextNode = node.next.getOrDefault(curChar, new Trie());
                node.next.put(curChar,nextNode);
                node = nextNode;
            }
            node.isEnd = true;
        }

        public Trie startWithPrefix(String prefix) {
            Trie node = this;
            for (int i = 0; i < prefix.length(); i++) {
                char curChar = prefix.charAt(i);
                Trie nextNode = node.next.getOrDefault(curChar, null);
                if (nextNode == null) return null;
                node = nextNode;
            }
            return node;
        }
    }

    public List<List<String>> solve(List<String> strings,String target) {
        //构建前缀树
        Trie root = new Trie();
        for (String str : strings) {
            root.insert(str);
        }
        //结果集
        List<List<String>> res = new ArrayList<>();
        //前缀变化
        for (int i = 0; i < target.length(); i++) {
            String curPrefix = target.substring(0, i + 1);
            //去前缀树中查询这个前缀的下一个节点
            Trie prefixNextNode = root.startWithPrefix(curPrefix);
            if (prefixNextNode == null) continue;
            StringBuilder curSb = new StringBuilder(curPrefix);
            List<String> curList = new ArrayList<>();
            //深搜
            dfs(prefixNextNode,curSb,curList);
            res.add(curList);
        }
        return res;
    }

    private void dfs(Trie prefixNextNode, StringBuilder curSb, List<String> curList) {
        if (curList.size() >= 3) return;
        if (prefixNextNode.isEnd == true) {
            if (curList.size() < 3) {
                curList.add(curSb.toString());
            }
            return;
        }
        List<Character> keyList = new ArrayList<>(prefixNextNode.next.keySet());
        //按字典顺序排序
        keyList.sort((c1,c2)->c1 - c2);
        //从小到大依次深搜
        for (char ch : keyList) {
            Trie nextNode = prefixNextNode.next.get(ch);
            curSb.append(ch);
            dfs(nextNode,curSb,curList);
            //消除本层影响
            curSb.deleteCharAt(curSb.length() - 1);
        }
    }

    @Test
    public void test() {
        List<String> list = new ArrayList<>();
        list.add("mongo");
        list.add("module");
        list.add("moulai");
        list.add("mockey");

        String target = "moulai";
        List<List<String>> solve = solve(list, target);
        System.out.println(solve);
    }
}
